Computer Network Background
A computer network is simply a collection of autonomous computers connected together to permit sharing of hardware and software resources, and to increase overall reliability. The qualifying term "local area" is usually applied to computer networks in which the computers are located in a single building or in nearby buildings, such as on a college campus or at a single corporate site. When the computers are further apart, the terms "wide area network" or "long haul network" are used, but the distinction is one of degree and the definitions sometimes overlap.
A bridge is a device that is connected to at least two LANs and serves to pass message frames or packets between LANs, such that a source station on one LAN can transmit data to a destination station on another LAN, without concern for the location of the destination. Bridges are useful and necessary network components, principally because the total number of stations on a single LAN is limited. Bridges can be implemented to operate at a selected layer of protocol of the network. A detailed knowledge of network architecture is not needed for an understanding of this invention, but a brief description follows by way of further background.
At the heart of any computer network is a communication protocol. A protocol is a set of conventions or rules that govern the transfer of data between computer devices. The simplest protocols define only a hardware configuration, while more complex protocols define timing, data formats, error detection and correction techniques and software structures.
Computer networks almost universally employ multiple layers of protocols. A low-level physical layer protocol assures the transmission and reception of a data stream between two devices. Data packets are constructed in a data link layer. Over the physical layer, a network and transport layer protocol governs transmission of data through the network, thereby ensuring end-to end reliable data delivery.
The most common physical networking protocol or topology for small networks is Ethernet, developed by Xerox. When a node possesses a packet to be transmitted through the network, the node monitors the backbone and transmits when the backbone becomes clear. There is no central backbone master device to grant requests to gain access to the backbone. While this type of multipoint topology facilitates rapid transmission of data when the backbone is lightly utilized, packet collisions may occur when the backbone is heavily utilized. In such circumstances, there is a greater chance that multiple nodes will detect that the backbone is clear and transmit their packets coincidentally. If packets are impaired in a collision, the packets are retransmitted until transmission is successful.
Another conventional physical protocol or topology is Token Ring, developed by IBM. This topology employs a "token" that is passed unidirectionally from node to node around an annular backbone. The node possessing the token is granted exclusive access to the backbone for a single packet transfer. While this topology reduces data collisions, the latency incurred while each node waits for the token translates into a slower data transmission rate than Ethernet when the network is lightly utilized.
As computer networks have developed, various approaches have been used in the choice of communication medium, network topology, message format, protocols for channel access, and so forth. Some of these approaches have emerged as de facto standards, but there is still no single standard for network communication. However, a model for network architectures has been proposed and widely accepted. It is known as the International Standards Organization (ISO) Open Systems Interconnection (OSI) reference model. The OSI reference model is not itself a network architecture. Rather it specifies a hierarchy of protocol layers and defines the function of each layer in the network. Each layer in one computer of the network carries on a conversation with the corresponding layer in another computer with which communication is taking place, in accordance with a protocol defining the rules of this communication. In reality, information is transferred down from layer to layer in one computer, then through the channel medium and back up the successive layers of the other computer. However, for purposes of design of the various layers and understanding their functions, it is easier to consider each of the layers as communicating with its counterpart at the same level, in a "horizontal" direction.
The lowest layer defined by the OSI model is called the physical layer, and is concerned with transmitting raw data bits over the communication channel. Design of the physical layer involves issues of electrical, mechanical or optical engineering, depending on the medium used for the communication channel. The layer next to the physical layer is called the data link layer. The main task of the data link layer is to transform the physical layer, which interfaces directly with the channel medium, into a communication link that appears error-free to the next layer above, known as the network layer. The data link layer performs such functions as structuring data into packets or frames, and attaching control information to the packets or frames, such as checksums for error detection, and packet numbers.
Although the data link layer is primarily independent of the nature of the physical transmission medium, certain aspects of the data link layer function are more dependent on the transmission medium. For this reason, the data link layer in some network architectures is divided into two sublayers: a logical link control sublayer, which performs all medium-independent functions of the data link layer, and a media access control (MAC) sublayer. This sublayer determines which station should get access to the communication channel when there are conflicting requests for access. The functions of the MAC layer are more likely to be dependent on the nature of the transmission medium.
Bridges may be designed to operate in the MAC sublayer. Further details may be found in "MAC Bridges," P802.1D/D6, September 1988, a draft publication of IEEE Project 802 on Local and Metropolitan Area Network Standards, or in later drafts of this document.
The basic function of a bridge is to listen "promiscuously," i.e., to all message traffic on all LANs to which it is connected, and to forward each message it hears onto LANs other than the one from which the message was heard. Bridges also maintain a database of station locations, derived from the content of the messages being forwarded. Bridges are connected to LANs by paths known as "links." After a bridge has been in operation for some time, it can associate practically every station with a particular link connecting the bridge to a LAN, and can then forward messages in a more efficient manner, transmitting only over the appropriate link. The bridge can also recognize a message that does not need to be forwarded, because the source and destination stations are both reached through the same link. Except for its function of "learning" station locations, or at least station directions, the bridge operates basically as a message repeater.
As network topologies become more complex, with large numbers of LANs, and multiple bridges interconnecting them, operational difficulties can ensue if all possible LAN bridging connections are permitted. In particular, if several LANs are connected by bridges to form a closed loop, a message may be circulated back to the LAN from which it was originally transmitted, and multiple copies of the same message will be generated. In the worst case, messages will be duplicated to such a degree that the networks will be effectively clogged with these messages and unable to operate at all.
To prevent the formation of closed loops in bridged networks, IEEE draft publication P802.1D, referred to above, proposes a standard for a spanning tree algorithm that will connect the bridged network into a tree configuration, containing no closed loops, and spanning the entire network configuration. The spanning tree algorithm is executed periodically by the bridges on the interconnected network, to ensure that the tree structure is maintained, even if the physical configuration of the network changes. Basically, the bridges execute the spanning tree algorithm by sending special messages to each other to establish the identity of a "root" bridge. The root bridge is selected, for convenience, as the one with the smallest numerical identification. The algorithm determines which links of the bridges are to be active and which are to be inactive, i.e., disabled, in configuring the tree structure. One more piece of terminology is needed to understand how the algorithm operates. Each LAN has a "designated" link, which means that one of the links connectable to the LAN is designated to carry traffic toward and away from the root bridge. The basis for this decision is similar to the basis for selecting the root bridge. The designated link is the one providing the least costly (shortest) path to the root bridge, with numerical bridge identification being used as a tie-breaker. Once the designated links are identified, the algorithm chooses two types of links to be activated or closed: first, for each LAN its designated link is chosen, and second, for each bridge a link that forms the "best path" to the root bridge is chosen, i.e., a link through which the bridge received a message giving the identity of the root bridge. All other links are inactivated. Execution of the algorithm results in interconnection of the LANs and bridges in a tree structure, i.e., one having no closed loops.
The "Internet" is a collection of networks, including Arpanet, NSFnet, regional networks such as NYsernet, local networks at a number of university and research institutions, and a number of military networks. The protocols generally referred to as TCP/IP were originally developed for use only through Arpanet and have subsequently become widely used in the industry. The protocols provide a set of services that permit users to communicate with each other across the entire Internet. The specific services that these protocols provide are not important to the present invention, but include file transfer, remote log-in, remote execution, remote printing, computer mail, and access to network file systems.
The basic function of the Transmission Control Protocol (TCP) is to make sure that commands and messages from an application protocol, such as computer mail, are sent to their desired destinations. TCP keeps track of what is sent, and retransmits anything that does not get to its destination correctly. If any message is too long to be sent as one "datagram," TCP will split it into multiple datagrams and makes sure that they all arrive correctly and are reassembled for the application program at the receiving end. Since these functions are needed for many applications, they are collected into a separate protocol (TCP) rather than being part of each application. TCP is implemented in the transport layer of the OSI reference model.
The Internet Protocol (IP) is implemented in the network layer of the OSI reference model, and provides a basic service to TCP: delivering datagrams to their destinations. TCP simply hands IP a datagram with an intended destination; IP is unaware of any relationship between successive datagrams, and merely handles routing of each datagram to its destination. If the destination is a station connected to a different LAN, the IP makes use of routers to forward the message.
TCP/IP frequently uses a slight deviation from the seven-layer OSI model in that it may have five layers. These five layers are combinations and derivatives of the seven-layer model as shown in FIG. 1. The five layers are as follows:
Layer 5--The Application Layer. Applications such as ftp, telnet, SMTP, and NFS relate to this layer.
Layer 4--The Transport Layer. In this layer, TCP and UDP add transport data to the packet and pass it to layer 3.
Layer 3--The Internet Layer. When an action is initiated on a local host (or initiating host) that is to be performed or responded to on a remote host (or receiving host), this layer takes the package from layer 4 and adds IP information before passing it to layer 2.
Layer 2--The Network Interface Layer. This is the network device as the host, or local computer, sees it and it is through this medium that the data is passed to layer 1.
Layer 1--The Physical Layer. This is literally the Ethernet or Serial Line Interface Protocol (SLIP) itself.
At the receiving host the layers are stripped one at a time, and their information is passed to the next highest level until it again reaches the application level. If a gateway exists between the initiating and receiving hosts, the gateway takes the packet from the physical layer, passes it through a data link to the IP physical layer to continue, as is shown in FIG. 2. As a message is sent from the first host to the second, gateways pass the packet along by stripping off lower layers, readdressing the lower layer, and then passing the packet toward its final destination.
A router, like a bridge, is a device connected to two or more LANs. Unlike a bridge, however, a router operates at the network layer level, instead of the data link layer level. Addressing at the network layer level makes use of a 32-bit address field for each host, and the address field includes a unique network identifier and a host identifier within the network. Routers make use of the destination network identifier in a message to determine an optimum path from the source network to the destination network. Various routing algorithms may be used by routers to determine the optimum paths. Typically, routers exchange information about the identities of the networks to which they are connected.
When a message reaches its destination network, a data link layer address is needed to complete forwarding to the destination host. Data link layer addresses are 48 bits long and are globally unique, i.e., no two hosts, wherever located, have the same data link layer address. There is a protocol called ARP (address resolution protocol), which obtains a data link layer address from the corresponding network layer address (the address that IP uses). Typically, each router maintains a database table from which it can look up the data link layer address, but if a destination host is not in this ARP is database, the router can transmit an ARP request. This message basically means: "will the host with the following network layer address please supply its data link layer address." Only the addressed destination host responds, and the router is then able to insert the correct data link layer address into the message being forwarded, and to transmit the message to its final destination.
IP routing specifies that IP datagrams travel through internetworks one hop at a time (next hop routing) based on the destination address in the IP header. The entire route is not known at the outset of the journey. Instead, at each stop, the next destination (or next hop) is calculated by matching the destination address within the datagram's IP header with an entry in the current node's (typically but not always a router) routing table.
Each node's involvement in the routing process consists only of forwarding packets based on internal information resident in the router, regardless of whether the packets get to their final destination. To extend this explanation a step further, IP routing does not alter the original datagram. In particular, the datagram source and destination addresses remain unaltered. The IP header always specifies the IP address of the original source and the IP address of the ultimate destination.
When IP executes the routing algorithm it computes a new address, the IP address of the machine/router to which the datagram should be sent next. This algorithm uses the information from the routing table entries, as well as any cached information local to the router. This new address is most likely the address of another router/gateway. If the datagram can be delivered directly (the destination network is directly attached to the current host) the new address will be the same as the destination address in the IP header.
The next hop address defined by the method above is not stored in their IP datagram. There is no reserved space to hold it and it is not "stored" at all. After executing the routing algorithm (the algorithm is specific to the vendor/platform) to define the next hop address to the final destination. The IP protocol software passes the datagram and the next hop address to the network interface software responsible for the physical network over which the datagram must now be sent.
The network interface software binds the next hop address to a physical address (this physical address is discovered via address resolution protocols (ARP, RARP, etc.), forms a frame (Ethernet, SMDS, FDDI, etc.--OSI layer 2 physical address) using the physical address, places the datagram in the data portion of the frame, and sends the result out over the physical network interface through which the next hop gateway is reached. The next gateway receives the datagram and the foregoing process is repeated.
In addition, the IP does not provide for error reporting back to the source when routing anomalies occur. This task is left to another Internet protocol, the Internet Control Message Protocol (ICMP).
A router will perform protocol translation. One example is at layers 1 and 2. If the datagram arrives via an Ethernet interface and is destined to exit on a serial line, for example, the router will strip off the Ethernet header and trailer, and substitute the appropriate header and trailer for the specific network media, such as SMDS, by way of example.
A route policy may be used instead of routing table entries to derive the next hop address. In the system and methodology of the present invention, the source address is tested to see in which ISP address range it falls. Once the ISP address range is determined the packet is then routed to the next hop address associated with the specific ISP.
Data communications network services have two categories of call establishment procedures: connection-oriented and connectionless.
Connection-oriented network services require that users establish a single distinct virtual circuit before the data can be transmitted. This circuit then defines a fixed path through the network that all traffic follows during the session. Several packet switching services are connection-oriented, notably X.25 and Frame Relay. X.25 is the slower of the services, but has built-in error correction--enough for its performance not to depend on clean, high-quality optical fiber lines. Frame relay, regarded as the first generation of fast packet technology, is well-suited for high-speed bursty data communication applications.
Connectionless network services, by contrast, let each packet of a communications session take a different, independent path through the network. One example is the Switched Multimegabit Data Service (SMDS), a possible precursor to broadband ISDN. This fast-packet service supports data rates ranging from the T1 rate of 1.544 Mb/s up to 1 Gb/s. The SMDS transport system architecture is defined by IEEE 802.6 Metropolitan Area Network standards.
Eventually, SMDS is expected to operate at rates of 51.85 Mb/s to 9.953 Gb/s specified by the family of standards known in North America as Synchronous Optical Network (SONET). Synchronous Digital Hierarchy (SDH) is an ITU recommendation that grew out of and includes the specifications of SONET.
The process of routing packets over the Internet is also considered a connectionless network service. The Internet Protocol (IP) addresses packets from sender to receiver. It is still used mostly in conjunction with the Transmission Control Protocol (TCP), which establishes a connection between end users to manage the traffic flow and ensures the data are correct, providing end-to-end reliability. The combination, known as TCP/IP, is the Internet's main backbone protocol suite.
Telephone Network Control
All telecommunications systems having multiple switching offices require signaling between the offices. Telephone networks require signaling between switching offices for transmitting routing and destination information, for transmitting alerting messages such as to indicate the arrival of an incoming call, and for transmitting supervisor information, e.g., relating to line status. Signaling between offices can use `in-band` transport or `out-of-band` transport.
In-band signaling utilizes the same channel that carries the communications of the parties. In a voice telephone system, for example, one of the common forms of in-band signaling between offices utilizes multi-frequency signaling over voice trunk circuits. The same voice trunk circuits also carry the actual voice traffic between switching offices. In-band signaling, however, tends to be relatively slow and ties up full voice channels during the signaling operations. In telephone call processing, a substantial percentage of all calls go unanswered because the destination station is busy. For in-band signaling, the trunk to the end office switching system serving the destination is set-up and maintained for the duration of signaling until that office informs the originating office of the busy line condition. As shown by this example, in-band signaling greatly increases congestion on the traffic channels, that is to say, the voice channels in the voice telephone network example. In-band signaling also is highly susceptible to fraud because hackers have developed devices which mimic in-band signaling.
Out-of-band signaling evolved to mitigate the problems of in-band signaling. Out-of-band signaling utilizes separate channels, and in many cases separate switching elements. As such, out-of-band signaling reduces congestion on the channels carrying the actual communication traffic. Also, messages from the end users always utilize an in-band format and remain in-band, making it virtually impossible for an end user to simulate signaling messages which ride on an out-of-band channel or network. Out-of-band signaling utilizes its own signal formats and protocols and is not constrained by protocols and formats utilized for the actual communication, therefore out-of-band signaling typically is considerably faster than in-band signaling.
Out of band signaling networks typically include data links and one or more packet switching systems. Out-of-band signaling for telephone networks is often referred to as Common Channel Signaling (CCS) or Common Channel Interoffice Signaling (CCIS). Most such signaling communications for telephone networks utilize signaling system 7 (SS7) protocol. An SS7 compliant CCIS network comprises data switching systems designated Signal Transfer Points (STPs) and data links between the STPs and various telephone switching offices of the network. In advanced versions of the telephone network including high level control nodes, identified as Service Control Points (SCPs) or Integrated Service Control Points (ISCPs), the CCIS network also includes data links connecting the high level control nodes to one or more of the STPs.
The STPs are program controlled packet data switching systems. In operation, an STP will receive a packet data message from another node of the network, for example from an end office switching system. The STP analyzes point code information in the packet and routes the packet according to a translation table stored within the STP. This translation table is static. Any packet having a particular point code is output on a port going to the next CCIS signaling node specified by translation of that point code.
The development of the CCIS network has recently permitted the offering of a number of new service features provided by centralized program control from a high level control point. Such an enhanced telephone network is often termed an Advanced Intelligent Network (AIN). In an AIN type system, local and/or toll offices of the public telephone network detect one of a number of call processing events identified as AIN "triggers". For ordinary telephone service calls, there would be no event to trigger AIN processing; and the local and toll office switches would function normally and process such calls without referring to the central database for instructions. An office which detects a trigger will suspend call processing, compile a call data message and forward that message via the CCIS signaling network to an Integrated Service Control Point (ISCP) which includes a Multi-Services Application Platform (MSAP) database. If needed, the ISCP can instruct the central office to obtain and forward additional information. Once sufficient information about the call has reached the ISCP, the ISCP accesses its stored data tables in the MSAP database to translate the received message data into a call control message and returns the call control message to the office of the network via CCIS link. The network offices then use the call control message to complete the particular call. An AIN type network for providing an Area Wide Centrex service was disclosed and described in detail in commonly assigned U.S. Pat. No. 5,247,571 to Kay et al., the disclosure of which is entirely incorporated herein by reference. Existing AIN type systems, such as disclosed in the Kay et al. Patent, utilize the routing functionality of the STPs in the CCIS network as described above. Every time a specified switching office launches a query for an identified ISCP, the translation table in the STP(s) of the CCIS network causes the STP(s) to route the query message to that ISCP.
The CCIS and AIN which have been described provide effective and efficient connection oriented signaling between switches in modern telephone networks. However, such control is not available in the United States on a nationwide basis and is not available internationally for a variety of reasons. Connections between Interexchange Carriers (IXCs) and Local Exchange Carriers (LECs) in the United States are still made to a significant extent with in-band signaling. This requires inefficient use of circuit time of voice trunks and is vulnerable to fraud. The inefficiencies are particularly aggravated where international and particularly transoceanic communications are involved.